import java.time.LocalDate;
import java.time.format.DateTimeFormatterBuilder;
import java.util.Calendar;

/**
 * @author kahoChan
 * @date 2020/10/30
 */
public class _34_在排序数组中查找元素的第一个和最后一个位置 {
    /**
     * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
     * <p>
     * 你的算法时间复杂度必须是 O(log n) 级别。
     * <p>
     * 如果数组中不存在目标值，返回 [-1, -1]。
     * <p>
     * 示例 1:
     * <p>
     * 输入: nums = [5,7,7,8,8,10], target = 8
     * 输出: [3,4]
     * 示例 2:
     * <p>
     * 输入: nums = [5,7,7,8,8,10], target = 6
     * 输出: [-1,-1]
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] searchRange(int[] nums, int target) {
        int f = searchF1(nums,target);
        if (f == -1) {
            return new int[]{-1,-1};
        }
        int l = searchL1(nums, target);
        return new int[]{f, l};
    }

    private static int searchL1(int[] nums, int target) {
        int l = 0, r = nums.length-1;
        while (l<r){
            int mid = l + (r - l+1) / 2;
            if (nums[mid]>target) {
                r = mid-1;
            }else {
                l = mid;
            }
        }
        if (r<0 || nums[r] != target){
            return -1;
        }
        return r;

    }

    private static int searchF1(int[] nums, int target) {
        int l = 0, r = nums.length-1;
        while (l<r){
            int mid = l + (r - l) / 2;
            if (nums[mid]<target) {
                l = mid+1;
            }else {
                r = mid;
            }
        }
        if (l==nums.length || nums[l]!=target){
            return -1;
        }
        return l;
    }


    public static int[] searchRange2(int[] nums, int target) {
        if (nums.length==0) {
            return new int[]{-1,-1};
        }
        int f = searchF(nums, target);
        int r = searchR(nums, target);

        return new int[]{f,r};
    }

    private static int searchR(int[] nums, int target) {
        int l = 0, r = nums.length-1;
        while (l<r){
            int mid = l + ((r - l+1) >> 1);
            System.out.println("left = " + l + ", right = " + r + ", mid = " + mid);
            if(nums[mid] > target){
                r= mid -1;
            }else {
                l=mid;
            }
        }
        if (nums[r]!=target){
            return -1;
        }
        return r;
    }

    private static int searchF(int[] nums, int target) {
        int l = 0, r = nums.length-1;
        while (l<r){
            int mid = l + ((r - l) >> 1);
            if (nums[mid]<target) {
                l = mid+1;
            }else {
                r = mid;
            }
        }
        if (nums[l]!=target){
            return -1;
        }
        return l;
    }


    public static int[] searchRange1(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }
        int firstIdx = searchFirstIdx(nums, target);
//        if (firstIdx == -1) {
//            return new int[]{-1, -1};
//        }
        int lastIdx = searchLastIdx(nums, target);
        return new int[]{firstIdx, lastIdx};
    }

    private static int searchLastIdx(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                start = mid + 1;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else if (nums[mid] > target) {
                end = mid - 1;
            }
        }
        if (start == 0 || nums[start - 1] != target) {
            return -1;
        }
        return start - 1;
    }

    private static int searchFirstIdx(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                end = mid - 1;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else if (nums[mid] > target) {
                end = mid - 1;
            }
        }
        if (start >= nums.length || nums[start] != target) {
            return -1;
        }
        return start;
    }

    public static void main(String[] args) {
        int[] nums = {5,7,7,8,8,10};
//        int[] nums = {2, 2, 2};
        int target = 8;
//        int i = searchFirstIdx(nums, target);
        int[] ints = searchRange(nums, target);
//        int i = searchLastIdx(nums, target);
    }
}
